
\newpage
\section{递归与动态规划}

递归的要诀是：只关注问题和子问题的递推关系（类似递推数列的递推关系）和递归出口；不要陷入递归递归再递归的逻辑漩涡中。

递归决定了怎么尝试的问题; 动态规划决定了怎么避免重复计算的问题

\textbf{动态规划的中间结构,可变参数的集合}
\begin{enumerate}
	\item 多维数组
	\begin{itemize}
		\item 一维数组,递归过程中的一个变量的改变;还需要确认是否包含边界N的问题,确认填充数据的方向
		\item 二维数组,递归过程中的两个变量的改变;还需要确认是否包含边界N的问题
		
		\begin{tikzpicture}
			\foreach \x in {0,1,2,...,12}
			\foreach \y in {0,1,...,5}
			{
				\draw (\x,\y) +(-.5,-.5) rectangle ++(.5,.5);
				\draw (\x,\y) node{\x,\y};
			}
		\end{tikzpicture}
		
		\item 三维数组,递归过程中的三个变量的改变;还需要确认是否包含边界N的问题
		\item 多维数组等,递归过程中的多个变量的改变;还需要确认是否包含边界N的问题
	\end{itemize}
	\item 其他结构,可以是一个Map,Set,List,或者一个Dto的复合结构
\end{enumerate}

\subsection{从左至右的尝试模型}
\subsubsection{背包问题}
给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？

weight 物品的重量数组

\begin{tikzpicture}
	\foreach \x in {1,2,...,7}
	\foreach \y in {0}
	{
		\draw (\x,\y) +(-.5,-.5) rectangle ++(.5,.5);
		\draw (\x,\y) node{\x};
	}
\end{tikzpicture}

value 物品的价值数组

\begin{tikzpicture}
	\foreach \x in {0,1,2,...,6}
	\foreach \y in {0}
	{
		\draw (\x,\y) +(-.5,-.5) rectangle ++(.5,.5);
		%\draw (\x,\y) node{\x};
	}
	\draw (0,0) node{100};
	\draw (1,0) node{30};
	\draw (2,0) node{60};
	\draw (3,0) node{10};
	\draw (4,0) node{20};
	\draw (5,0) node{40};
	\draw (6,0) node{70};
\end{tikzpicture}

bag 的所能容纳的重量为10,在指定的容量内,所能获取的最大的价值

\textbf{动态规划问题图解}

\begin{tikzpicture}[scale=0.8,fill=red] % 设置绘图的比例
	
	% 画 x 轴
	\draw[->] (-2.5,0) -- (7,0) node[right] {$cur$};
	% 画 y 轴
	\draw[->] (0,-2.5) -- (0,11) node[above] {$rest$};
	
	% 添加网格
	\draw[help lines, step=1cm, gray!50] (-2,-2) grid (6,10);
	
	% 添加坐标轴上的刻度
	\foreach \x in {-2,...,7}
	\draw (\x cm,1pt) -- (\x cm,-1pt) node[anchor=north] {$\x$};
	\foreach \y in {-2,...,10}
	\draw (1pt,\y cm) -- (-1pt,\y cm) node[anchor=east] {$\y$};
	\fill (0cm,10cm) circle(10pt);
	
	\draw (6,0) node[text=red]{0};
	\draw (6,1) node[text=red]{0};
	\draw (6,2) node[text=red]{0};
	\draw (6,3) node[text=red]{0};
	\draw (6,4) node[text=red]{0};
	\draw (6,5) node[text=red]{0};
	\draw (6,6) node[text=red]{0};
	\draw (6,7) node[text=red]{0};
	\draw (6,8) node[text=red]{0};
	\draw (6,9) node[text=red]{0};
	\draw (6,10) node[text=red]{0};
\end{tikzpicture}

\subsubsection{数值到字符串的转换问题}
 通过递归算法，‌可以将一个整数递归地分解为单个数字，‌并将这些数字按照顺序拼接成字符串,1~26 对应A`Z,给定一组数值,如 $123123$ 可以拼接为多少不重复的字母的组合数
 

\begin{tikzpicture}
	\foreach \x in {1,2,...,6}
	\foreach \y in {0}
	{
		\draw (\x,\y) +(-.5,-.5) rectangle ++(.5,.5);
		
	}
	\draw (1,0) node{1};
	\draw (2,0) node{2};
	\draw (3,0) node{3};
	\draw (4,0) node{1};
	\draw (5,0) node{2};
	\draw (6,0) node{3};
\end{tikzpicture}

\textbf{动态规划问题,图解}

\begin{tikzpicture}
	\foreach \x in {1,2,...,6}
	\foreach \y in {0}
	{
		\draw (\x,\y) +(-.5,-.5) rectangle ++(.5,.5);
		
	}
	\draw (6,0) node{1};
\end{tikzpicture}


\subsection{范围上的尝试模型}

\subsubsection{两人抽取纸牌问题}
给定一个整形数组arr，代表数值不同的纸牌，
条件：玩家A、B每次依次拿走一张（A先拿），每次只能从最左、最右拿一张
要求：假设A、B都很聪明理智，返回最后获胜者的分数

\begin{tikzpicture}
	\foreach \x in {1,2,...,4}
	\foreach \y in {0}
	{
		\draw (\x,\y) +(-.5,-.5) rectangle ++(.5,.5);
		
	}
	\draw (1,0) node{1};
	\draw (2,0) node{100};
	\draw (3,0) node{4};
	\draw (4,0) node{7};
\end{tikzpicture}

\textbf{动态规划问题,图解}

因为存在两个递归过程,所以需要两个 dp 数组, 两个变量的改变,所以需要dp 是一个二维数组

\begin{tikzpicture}[scale=0.8,fill=red] % 设置绘图的比例
	
	% 画 x 轴
	\draw[->] (-2.5,0) -- (5,0) node[right] {$L$};
	% 画 y 轴
	\draw[->] (0,-2.5) -- (0,5) node[above] {$R$};
	
	% 添加网格
	\draw[help lines, step=1cm, gray!50] (-2,-2) grid (4,4);
	
	% 添加坐标轴上的刻度
	\foreach \x in {-2,...,5}
	\draw (\x cm,1pt) -- (\x cm,-1pt) node[anchor=north] {$\x$};
	\foreach \y in {-2,...,5}
	\draw (1pt,\y cm) -- (-1pt,\y cm) node[anchor=east] {$\y$};
	
	
	% 绘制 L = R 的边界线
	\draw[dashed] (0,0) -- (5,5);
	
	\draw (1,1) node{1};
	\draw (2,2) node{100};
	\draw (3,3) node{4};
	\draw (4,4) node{7};
	
	% L > R 的无效区域的设置
	%\fill (0cm,10cm) circle(10pt);
	\foreach \L in {1,...,4}{
		\foreach \R in {1,...,4}{
			\ifthenelse{\L > \R}{
				\draw (\L,\R) node{x};
			}
		}
	}
	                               

\end{tikzpicture}
\begin{tikzpicture}[scale=0.8,fill=red] % 设置绘图的比例
	
	% 画 x 轴
	\draw[->] (-2.5,0) -- (5,0) node[right] {$L$};
	% 画 y 轴
	\draw[->] (0,-2.5) -- (0,5) node[above] {$R$};
	
	% 添加网格
	\draw[help lines, step=1cm, gray!50] (-2,-2) grid (4,4);
	
	% 添加坐标轴上的刻度
	\foreach \x in {-2,...,5}
	\draw (\x cm,1pt) -- (\x cm,-1pt) node[anchor=north] {$\x$};
	\foreach \y in {-2,...,5}
	\draw (1pt,\y cm) -- (-1pt,\y cm) node[anchor=east] {$\y$};
	%\fill (0cm,10cm) circle(10pt);
	
		
	\draw[dashed] (0,0) -- (5,5);
	%\fill (0cm,10cm) circle(10pt);
	\draw (1,1) node{0};
	\draw (2,2) node{0};
	\draw (3,3) node{0};
	\draw (4,4) node{0};
	
	% 绘制 L > R 属于无效区域
	\foreach \L in {1,...,4}{
		\foreach \R in {1,...,4}{
			\ifthenelse{\L > \R}{
				\draw (\L,\R) node {x};
			}
		}
	}
	
	
\end{tikzpicture}



\subsubsection{机器人的移动问题}
假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2
开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)
如果机器人来到1位置，那么下一步只能往右来到2位置；
如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
如果机器人来到中间位置，那么下一步可以往左走或者往右走；
规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
给定四个参数 N、M、K、P，返回方法数。
假设当前为如下值

\[
\text{总点位数 } M = 7, \quad
\text{当前位置 } N = 3, \quad
\text{停止位置 } P = 2, \quad
\text{剩余可移动步数 } K = 3
\]


\begin{tikzpicture}
	\foreach \x in {1,2,...,7}
	\foreach \y in {0}
	{
		\draw (\x,\y) +(-.5,-.5) rectangle ++(.5,.5);
		\draw (\x,\y) node{\x};
	}
\end{tikzpicture}

动态规划问题,图解

\begin{tikzpicture}[scale=0.8,fill=red] % 设置绘图的比例

	% 画 x 轴
	\draw[->] (-2.5,0) -- (7,0) node[right] {$cur$};
	% 画 y 轴
	\draw[->] (0,-2.5) -- (0,7) node[above] {$rest$};
	
	% 添加网格
	\draw[help lines, step=1cm, gray!50] (-7,-7) grid (7,7);
	
	% 添加坐标轴上的刻度
	\foreach \x in {-7,-6,...,7}
	\draw (\x cm,1pt) -- (\x cm,-1pt) node[anchor=north] {$\x$};
	\foreach \y in {-7,-6,...,7}
	\draw (1pt,\y cm) -- (-1pt,\y cm) node[anchor=east] {$\y$};
	%\fill (2cm,0cm) circle(10pt);
\end{tikzpicture}

\section{经典动态规划问题}
存在有限次数的枚举的行为, 记忆化搜索的又一次改进问题
\subsection{指定金额取硬币的组合数问题}
简单点说，就是给你一些硬币，这些硬币有很多个，现在问你，组成n分钱，可以有多少种组合方式。

通过不同数量的硬币探索可能的组合方法‌：还可以通过改变硬币的数量来探索不同的组合方法。例如，改变1元、5角、1角硬币的数量，观察可以通过多少种不同的方式组合成特定的面额。

假设当前给定的金币为,5,10,50,100 元, 拼凑30块的方法有多少种

\begin{tikzpicture}
	\foreach \x in {0,1,2,...,3}
	\foreach \y in {0}
	{
		\draw (\x,\y) +(-.5,-.5) rectangle ++(.5,.5);
		%\draw (\x,\y) node{\x};
	}
	\draw (0,0) node {5};
	\draw (1,0) node {10};
	\draw (2,0) node {50};
	\draw (3,0) node {100};
\end{tikzpicture}

\subsubsection{递归版本}
从索引0开始, 依次从0张,1张,2张....尝试,金额刚好相等就返回1,否则返回0;

索引自增1,不断进行上述行为; 直至所有的硬币都尝试完成

\subsubsection{动态规划1-dp表}
\begin{tikzpicture}[scale=0.4,fill=red] % 设置绘图的比例
	
	% 画 x 轴
	\draw[->] (-2.5,0) -- (5,0) node[right] {$cur$};
	% 画 y 轴
	\draw[->] (0,-2.5) -- (0,31) node[above] {$rest$};
	
	% 添加网格
	\draw[help lines, step=1cm, gray!50] (-7,-7) grid (4,30);
	
	% 添加坐标轴上的刻度
	\foreach \x in {-7,-6,...,5}
	\draw (\x cm,1pt) -- (\x cm,-1pt) node[anchor=north] {$\x$};
	\foreach \y in {-7,-6,...,31}
	\draw (1pt,\y cm) -- (-1pt,\y cm) node[anchor=east] {$\y$};

	
	\draw (4,0) node[text=red] {1};
	\fill (0cm,30cm) circle(10pt);
\end{tikzpicture}

\subsubsection{动态规划2-dp表-升级计算}
总是依赖上一行,但是如果计算过了,是可以避免重复计算,直接取最近的结果
\begin{tikzpicture}[scale=0.4,fill=red] % 设置绘图的比例
	
	% 画 x 轴
	\draw[->] (-2.5,0) -- (5,0) node[right] {$index$};
	% 画 y 轴
	\draw[->] (0,-2.5) -- (0,31) node[above] {$rest$};
	
	% 添加网格
	\draw[help lines, step=1cm, gray!50] (-7,-7) grid (4,30);
	
	% 添加坐标轴上的刻度
	\foreach \x in {-7,-6,...,5}
	\draw (\x cm,1pt) -- (\x cm,-1pt) node[anchor=north] {$\x$};
	\foreach \y in {-7,-6,...,31}
	\draw (1pt,\y cm) -- (-1pt,\y cm) node[anchor=east] {$\y$};
	
	% 标记起始点,终止点
	\draw (4,0) node[text=red] {1};
	\fill (0cm,30cm) circle(10pt);
	
	% 填充
\end{tikzpicture}